package _03LinkedList;
// add head
class _05DeleteSinglyLinkedList {
    // Singly linked list node in Java
    class Node {
        int data;
        Node next;
        Node(int d) {
            data = d;
            next = null;
        }
        Node() {}
    }
    Node head = new Node();
    // time complexity： O(1)
    // space complexity: O(1)
    // inserts a new node on the front of the list.
    public void push(int data) {
        // allocate new node
        Node newNode = new Node(data);

        // insert 1.add head
        newNode.next = head.next;
        head.next = newNode;
    }

    // time complexity： O(n)
    // space complexity: O(1)
    // delete key node in linked list（first node is head）
    void deleteNode(int key) {

        Node prev = head;
        // add head
        Node temp = head.next;

        while(temp != null && temp.data != key) {
            prev = temp;
            temp = temp.next;
        }
        // not found
        if(temp == null)
            return;
        // new link
        prev.next = temp.next;
        return;
    }

    public void printList() {
        Node temp = head.next;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }

    public static void main(String[] args) {
        _05DeleteSinglyLinkedList list = new _05DeleteSinglyLinkedList();

        list.push(3);
        list.push(9);
        list.push(5);
        list.push(8);
        list.push(2);
        System.out.print("Linked List: ");
        list.printList();
        System.out.println();

        list.deleteNode(11);
        System.out.print("after delete Linked List: ");
        list.printList();

    }
}

